//
//  322. 零钱兑换 322. 零钱兑换 322. 零钱兑换 322_零钱兑换.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/4.
/**
 1、定义状态
 2、设置初始值
 3、递推方程式
 */

import UIKit
/**
 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
 你可以认为每种硬币的数量是无限的。
 示例 1：
 输入：coins = [1, 2, 5], amount = 11
 输出：3
 解释：11 = 5 + 5 + 1
 示例 2：

 输入：coins = [2], amount = 3
 输出：-1
 示例 3：

 输入：coins = [1], amount = 0
 输出：0

 */
class ZhaoLingQian  { // 递归所有情况
    func QA() {
       let object = ZhaoLingQian()
       let result = object.coinChange([2], 3)
        print(result)
    }
     
    func coinChange(_ coins: [Int], _ amount: Int) -> Int {
        if amount < 1 {
            return Int.max
        }
        if coins.contains(amount) {
            return 1
        }
        var getMin = Int.max
        for coin in coins {
            getMin = min(coinChange(coins, amount - coin), getMin)
        }
        return getMin + 1
    }
}

class ZhaoLingQian1  { // 动态规划
    
    func QA() {
       let object = ZhaoLingQian1()
        // 1, 5, 20 ,25
        let result = object.coinChange([1, 5, 20 ,25], 19) // 7

        print(result)
    }
     
    func coinChange(_ coins: [Int], _ amount: Int) -> Int {
        if amount < 1 || coins.count == 0 {
            return -1
        }
        var dp = Array(repeating: 0, count: amount + 1)
        for i in 1...amount {
            var getMin = Int.max
            for coin in coins {
                if i < coin || dp[i - coin] < 0 { continue }
                getMin = min(getMin, dp[i - coin])
            }
//            if i >= 1 { getMin = min(getMin, dp[i - 1]) }
//            if i >= 5 { getMin = min(getMin, dp[i - 5]) }
//            if i >= 20 { getMin = min(getMin, dp[i - 20]) }
//            if i >= 25 { getMin = min(getMin, dp[i - 25]) }
            if getMin == Int.max {
                dp[i] = -1
            } else {
                dp[i] = getMin + 1
            }
        }
        return dp[amount]
    }
}

